A Public Key Infrastructure (“PKI”) is a set of protocols and conventions to facilitate secure and verifiable electronic communications between parties who may lack a safe channel or prior acquaintance history that they could use to verify each other's identity. The basic elements of PKI are pairs of keys, denoted “public” and “private,” with the property that a message encrypted with the public key can only be decrypted with the corresponding private key (and vice versa). A user with such a pair of keys can publish one (the “public” key) and encrypt his messages with the other (the “private” key); recipients of the messages can decrypt the messages with the public key and receive some assurance that the sender of the message knew the corresponding private key. The encryption with the private key functions as a cryptographic signature. In one common usage, a sender computes a cryptographic hash of a message and encrypts the hash with his private key. The message itself may be transmitted in plaintext with the encrypted hash appended. A recipient can decrypt the encrypted hash with the sender's public key and compare it with a hash of the message he computes himself to verify that the message was not altered and that the sender knew the corresponding private key.
The simple use of public and private keys described above is vulnerable to attack unless the message recipient has some way of associating the public key with the message sender. A Public Key Infrastructure addresses this problem by introducing a trusted third party called a Certificate Authority (“CA”). A CA has its own public and private keys, and performs the service of verifying the identity of a party who is associated with a public/private key pair. The CA produces a certificate containing the party's public key and identity information. The certificate is signed with the CA's private key, and can be verified with the CA's public key. Of course, the recipient must still have some way of establishing that the CA's public key belongs to the CA (and not to an impostor), but once this is established, messages from any sender who produces a certificate signed by the CA can be verified. The recipient need no longer verify each sender's public key individually. This fact makes it efficient and economical to go to the trouble of verifying the CA's keys, since this single verification automatically permits verification of messages from any user who has a certificate from the CA.
A Public Key Infrastructure may also define a mechanism for a CA to notify users of revoked certificates. For example, if a sender's private key is compromised by an attacker, the sender will want to disavow all messages signed by the private key after the compromise, and recipients will want to confirm the continued validity of sender certificates of messages they receive. This, too, can be accomplished with the assistance of the trusted CA. The CA publishes a list of revoked certificates (a certificate revocation list or “CRL”) containing identifiers of certificates that are no longer to be trusted. The CRL is signed by the CA to prevent attacks where arbitrary (uncompromised) certificates are announced as revoked.
Since a CA may issue tens or hundreds of millions of certificates, CRLs can be quite lengthy. Alternate one-at-a-time certificate validity checking protocols such as the Online Certificate Status Protocol (“OCSP,” described in Internet Engineering Task Force (“IETF”) Request for Comments (“RFC”) document number 2560, published June 1999) permit individual certificates (or small numbers of certificates) to be validated, but the computational cost of signing each OCSP response can become overwhelming and eliminate any savings over distributing the whole CRL. New, efficient methods of distributing information about valid and revoked certificates may be of value in this field.